1. Field of the Invention
The present invention relates to error detection and/or correction codes, and in particular to linear codes of Hamming type.
2. Description of the Related Art
The Hamming code is an error detection and correction code used in many fields, for example for data storage or transmission. Its use for the storage of data in a memory will be described, in the case where the data to be stored are in the form of 16-bit words.
Let X be the word to be stored. X can be represented by a vector Xe, the 16 components X0 to X15 of which correspond to the 16 bits of the word to be stored. Five error detection bits Ci (C0 . . . C4) are obtained by multiplying a parity control matrix H, called a Hamming matrix, of dimensions 5×16, by vector Xe in the form of a column vector.
FIG. 1A illustrates Hamming matrix H for 16 bits and FIG. 1B illustrates how to obtain the detection bits. Calling hij the elements of matrix H, the error detection bits Ci are given by:
      C    i    =            ∑              j        =        0            15        ⁢                  h        ij            ·              X        j            Xj being the j-th component of vector Xe.
In write mode, 21-bit words, formed of the 16 data bits Xj and of the 5 detection bits Ci, are written into the memory. In read mode, the read word includes 16 bits Xr corresponding to the data bits and 5 bits Cr corresponding to the detection bits. It is possible for Xr and Cr not to be equal to Xj and Ci if errors occur during transmission.
To detect and/or correct possible errors on the read bits, a syndrome S with five components S0, . . . S4 is calculated by multiplying a determined matrix H′ of dimensions 5×21 by a column vector with 21 components, including the 16 bits Xr and the 5 received bits Cr.
FIG. 2A illustrates matrix H′. The first 16 columns of matrix H′ correspond to the 16 columns of matrix H. The 5 following columns each include a single “1”. The 17-th column has its “1” on the first line, the 18-th column has its “1” on the second line, and so on until the 21rst column, which has its “1” on the fifth line. The last five columns of matrix H′ are used to determine possible errors in the detection bits.
FIG. 2B illustrates the calculation of syndrome S.
If syndrome S has all its components equal to 0, the storage occurs with no error and all the bits of the read word, be they data bits or detection bits, are correct.
If S is different from 0, the read word includes one or several errors. If a single bit of the read word is erroneous, the obtained syndrome enables correcting the error. Indeed, the obtained syndrome corresponds in this case to the column having had its elements multiplied by the erroneous bit. Thus, if the calculated syndrome is equal to:
      S    =          (                                    0                                                0                                                0                                                1                                                1                              )        ,the components (00011) of the syndrome correspond to the elements of the first column of the Hamming matrix, which means that the first bit, X0, is erroneous.
Similarly, if the calculated syndrome is equal to:
            S      ″        =          (                                    1                                                0                                                0                                                0                                                0                              )        ,and there is a single error in the read word, this means that the first detection bit C0 is erroneous.
A disadvantage of the above Hamming code is that it cannot detect two errors. For example, if an error has occurred on bits X1 and X2, the obtained syndrome is equal to the sum modulo 2 of the syndromes corresponding to errors on X1 and X2, that is, to: S′″=(00101)+(00110)=(00011). The obtained syndrome indicates an error on bit X0, which is wrong.
Indeed, the Hamming code is known to have a minimum code distance d=3 and a linear code like the Hamming code is known to be able to correct L errors and to detect L+1 errors if its minimum code distance d is strictly greater than 2L+1.
To improve the above code and turn it into a code having a minimum code distance equal to 4, it is known to add to the word to be stored a total parity bit P.
Total parity bit P is calculated by adding modulo 2 all the data bits and all the detection bits. The parity bit is added to the word to be stored, and the word to be stored, the detection bits, and the total parity bit are altogether stored.
In read mode, the read word is multiplied by parity control matrix H″ shown in FIG. 3A. Matrix H″ has one more line and one more column than matrix H′. Matrix H″ includes, to the top left, that is, on the first five lines and on the first 21 columns, a block identical to matrix H′. The last line D of matrix H″ only includes “is” and the last column of matrix H″ only includes “0s”, except for the last element of the column which contains a The obtained syndrome S′ is illustrated in FIG. 3B. Syndrome S′ includes six components S0 to S5, and is obtained by multiplying matrix H″ by a column vector including the 22 bits of the read word, formed of the 16 read data bits, followed by the five read detection bits, and by the read total parity bit.
The code thus obtained is a so-called “SEC-DED” code (“Single Error Correction”—“Double Error Detection”). This code can detect two errors in all cases, two errors being indicated by the fact that the last component of the syndrome, S5, is zero while the syndrome is different from the zero vector. However, the above code has the disadvantage of requiring the calculation of total parity bit P. This calculation is long, since it requires adding modulo 2 each of the data bits and of the detection bits. The calculation of the total parity bit cannot be performed in parallel with the detection bits, since its calculation requires the previous knowledge of the detection bits. Accordingly, it must be awaited that all detection bits have been calculated to calculate total parity bit P. This results in a loss of time, as well as in a high number of adders modulo 2.
Another disadvantage of the above-described Hamming code is that the Hamming matrix is neither symmetrical, nor regular. Considering that the elements of a column correspond to the binary representation of a number, the variation of this number is not regular and includes jumps. Such jumps make difficult the forming of a circuit implementing the Hamming code as well as the syndrome decoding, that is, the determination of the erroneous bit.